package 矩阵;

/**
 * 73:矩阵置零
 *  给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
 *
 *  基础暴力思路：
 *      首先编写一个方法，该方法是将当前元素的所在行和列的所有元素都设为 0
 *      然后遍历整个矩阵，如果当前元素为 0 ，则调用该方法
 *      时间复杂度：O(n^2)
 *   因为要使用原地算法，所以不能使用额外空间，必须基于原矩阵排序。
 *   思路：
 *      1、我们可以使用矩阵的第一行和第一列来记录哪些行和哪些列需要重置为0，从而避免使用额外的空间；
 *      2：首先要存储第一行与第一列的现有数据，我们可以使用row0和clo0标识来表示第一行和第一列是否存在0；
 *      3：然后再从第二行和第二列开始遍历数据，如果当前元素为0，则将当前元素下标所在的第一行首个[0][j]和第一列[i][0]首个的元素都设为0；
 *      4: 再次遍历，从第二行和第二列开始，根据第一行和第一列的标记元素来决定是否将某个元素设置为0；
 *      5： 最后再恢复第一行和第一列的数据，根据row0和clo0来还原第一行和第一列的数据，如果存在0，则统一设置为0；
 */
public class L_73 {
    public void setZeroes(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return;
        }
        int m = matrix.length;
        int n = matrix[0].length;

        //1: 记录第一行与第一列源数据是否存在0的标识
        boolean row0 = false;
        boolean clo0 = false;

        // 2: 记录第一行的是否存在0
        for (int j = 0; j < n; j++) {
            if(matrix[0][j] == 0){
                row0 = true;
                break;
            }
        }
        // 记录第一列是否存在0
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0){
                clo0 = true;
                break;
            }
        }

        // 3:从第二行与第二列开始遍历，如果当前元素为0，则将当前元素下标所在的第一行首个[0][j]和第一列[i][0]首个的元素都设为0
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if(matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        // 4: 遍历，从第二行与第二列开始，根据第一行和第一列的标记元素来决定是否将某个元素设置为0
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if(matrix[i][0] == 0 || matrix[0][j] == 0){
                    matrix[i][j] = 0;
                }
            }
        }
        // 5: 再根据row0和clo0来还原第一行和第一列的数据，如果存在0，则统一设置为0
        if(row0){
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
        if(clo0){
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}
